import javax.swing.tree.TreeNode;
import java.util.LinkedList;
import java.util.Queue;

//手动实现一个二叉树
public class BinaryTree implements IBinaryTree{

    // 前序遍历
    public void preOrder(treeNode root){
        //可以用子问题思路解决递归问题
        if(root == null){
            return;
        }
        System.out.print(root.data + " ");
        preOrder(root.left);
        preOrder(root.right);
    }
    // 中序遍历
    public void inOrder(treeNode root){
        if(root == null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.data + " ");
        inOrder(root.right);
    }
    // 后序遍历
    public void postOrder(treeNode root){
        if(root == null){
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.data + " ");
    }

    // 获取树中节点的个数
    public int size(treeNode root){
        //子问题思路，要想知道该节点下有几个节点，就要知道其左子树和右子树节点
        //最后在加一
        if(root == null){
            return 0;
        }
        return size(root.left)+size(root.right)+1;
    }

    int countLeaf;
    @Override
    // 获取叶⼦节点的个数
    public int getLeafNodeCount(treeNode root) {
        if(root == null){
            return 0;
        }
        if(root.left == null && root.right == null){
            countLeaf++;
        }
        getLeafNodeCount(root.left);
        getLeafNodeCount(root.right);
        return countLeaf;
    }

    // 获取第K层节点的个数
    @Override
    public int getKLevelNodeCount(treeNode root, int k) {
        //判断k是否合法
        if(k <= 0){
            throw new IndexOutOfBoundsException("k的值不合法，k为："+k);
        }
        if(root == null){
            return 0;
        }
        if(k == 1){
            return 1;
        }
        int leftNodeCount = getKLevelNodeCount(root.left, k-1);
        int rightNodeCount = getKLevelNodeCount(root.right, k-1);
        return leftNodeCount+rightNodeCount;
    }

    @Override
    //获取树的高度
    public int getHeight(treeNode root) {
        if(root == null){
            return 0;
        }
        int leftNodeCount = getHeight(root.left);
        int rightNodeCount = getHeight(root.right);
        return leftNodeCount > rightNodeCount ? leftNodeCount + 1 : rightNodeCount + 1;
    }

    @Override
    //在树中寻找元素
    public treeNode find(treeNode root, int val) {
        if(root == null){
            return null;
        }
        if(root.data == val){
            return root;
        }
        if(find(root.left, val)!=null){
            return find(root.left, val);
        }else if (find(root.right, val)!=null){
            return find(root.right, val);
        }
        return null;
    }

    //层序遍历
    @Override
    public void levelOrder(treeNode root) {
        if(root == null){
            return;
        }
        //首先需要一个队列
        Queue<treeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            treeNode cur = queue.poll();
            System.out.print(cur.data + " ");
            if(cur.left != null){
                queue.offer(cur.left);
            }
            if(cur.right != null){
                queue.offer(cur.right);
            }
        }
        System.out.println();
    }

    // 判断⼀棵树是不是完全⼆叉树
    @Override
    public boolean isCompleteTree(treeNode root) {
        if(root == null){
            return true;
        }
        Queue<treeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            treeNode cur = queue.poll();
            if(cur == null){
                break;
            }
            queue.offer(cur.left);
            queue.offer(cur.right);
        }
        //如果此时队列不为空，则可以知到这不是完全二叉树
        while(!queue.isEmpty()){
            treeNode node = queue.poll();
            if(node != null){
                return false;
            }
        }
        return true;
    }

}
